
/**
 * 冒泡排序
 * @param {*} arr 
 */
function bubbleSort(arr){
    for(let i=0; i<arr.length-1; i++){
        for(let j = 0; j<arr.length-i-1; j++){
            if(arr[j]>arr[j+1]){
                let temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
            }
        }
    }
}

/**
 * 选择排序
 * @param {*} arr 
 */
function selectSort(arr){
    for(let i=0; i<arr.length-1; i++){
        let min = i
        for(let j=i+1; j<arr.length; j++){
            if(arr[j]<arr[min]){
                min = j
            }
        }
        if(min != i){
            let temp = arr[min]
            arr[min] = arr[i]
            arr[i] = temp
        }
    }
}

/**
 * 插入排序
 * @param {*} arr 
 */
function insertSort(arr){
    for(let i=1; i<arr.length; i++){
        for(let j=i-1; j>=0; j--){
            if(arr[j+1]<arr[j]){
                swap(arr,j,j+1)
            }
        }
    }
}

/**
 * 希尔排序
 * @param {*} arr 
 */
function shellSort(arr){
    for(let d=Math.floor(arr.length/2); d>=1; d=Math.floor(d/2)){
        console.log(d)
        for(let i=d; i<arr.length; i++){
            for(let j=i-d; j>=0; j=j-d){
                if(arr[j+d]<arr[j]){
                    swap(arr,j,j+d)
                }
            }
        }
    }
    
}

/**
 * 归并排序
 * @param {*} arr 
 * @param {*} start 
 * @param {*} end 
 */
function mergeSort(arr,start,end){
    let middle = Math.floor((start+end)/2)
    if(start<end){
        mergeSort(arr,start,middle)
        mergeSort(arr,middle+1,end)
        merge(arr,start,middle,end)
    }
}


function merge(arr,start,middle,end){
    let tempArr = new Array(end-start+1)
    let i = start
    let j = middle+1
    let index = 0
    while(i<=middle && j<=end){
        if(arr[i]<arr[j]){
            tempArr[index++] = arr[i++]
        }else{
            tempArr[index++] = arr[j++]
        }
    }
    while(i<=middle){
        tempArr[index++] = arr[i++]
    }
    while(j<=end){
        tempArr[index++] = arr[j++]
    }

    for(let k=0; k<tempArr.length; k++){
        arr[k+start] = tempArr[k]
    }
}

/**
 * 快速排序
 * @param {*} arr 
 * @param {*} start 
 * @param {*} end 
 */
function quickSort(arr, start, end){

    if(start<end){
        let index = arr[start]
        let low = start
        let high = end
        while(low<high){
            while(low<high && index<=arr[high]){
                high--
            }
            arr[low] = arr[high]
            while(low<high && index>=arr[low]){
                low++
            }
            arr[high] = arr[low]
        }
        arr[low] = index
        quickSort(arr,start,low)
        quickSort(arr,low+1,end)
    }

}

/**
 * 堆排序（堆排序是从第一个元素开始排序的）
 * @param {*} arr   数组
 * @param {*} n  数组长度 
 */
function heapSort(arr, n){
    let i
    //n/2 选中最后一个双亲结点，构建每个双亲结点为大顶堆
    for(i=Math.floor(n/2); i>0; i--){
        headAdjust(arr,i,n)
    }

    
    for(i=n; i>1; i--){
        //交换第一个元素和最后一个元素
        swap(arr,1,i)
        //剩余元素再构建大顶堆
        headAdjust(arr,1,i-1)
    }
}

/**
 * 构建大顶堆
 * @param {*} arr   
 * @param {*} a     顶结点
 * @param {*} n     最后一个结点
 */
function headAdjust(arr, a, n){
    let i,temp
    temp = arr[a]
    for(let i=2*a; i<=n; i*=2){
        if(i<n && arr[i]<arr[i+1]){
            i++
        }
        if(temp>arr[i]){
            break
        }
        arr[a] = arr[i]
        a = i
    }
    arr[a] = temp
}

function swap(arr,i,j){
    let temp = arr[j]
    arr[j] = arr[i]
    arr[i] = temp
}


// let arr = [-1,1,6,4,5,2,9,3,0]
// heapSort(arr,arr.length-1)
// console.log(arr)

let obj = {
    a: 2,
    b: {},
    foo: function(){
        console.log(this.a)
    }
}
obj.b = obj.foo
let c = obj.foo
c()